\begin{frame}[allowframebreaks]
\frametitle{Tiling automaton}


\begin{define}[Next-position function \cite{journals/tcs/AnselmoGM09}]
	A partial function $f: \mathbb{N}^4 \rightarrow \mathbb{N}^2$ is called next-position function, if any defined quadruple $(i, j, m, n)$ is only using positions $(i, j) \in P(n, m)$. 
	
	A sequence of visited positions is of f at step k starting from $(i_0, j_0)$ is denoted by $V_{f, k}(m, n) = (v_1(m, n), v_2(m, n), \dots, v_k(m, n))$ where 
	\begin{itemize}
		\item $v_0(m, n) = (i_0, j_0)$
		\item $v_h(m, n) = f(i, j, m, n)$ with $(i, j) = v_{h - 1}(m, n)$ for $h = 2, \dots, k$. 
	\end{itemize}
\end{define}

\begin{Example}
\[f(1, 1, 3, 3) = (2, 1), f(2, 1, 3, 3) = (3, 1), f(3, 1, 3, 3) = (3, 2)\]

Then $V_{f, 3} = ((2, 1), (3, 1), (3, 2))$ with starting position $(2, 1)$.
\end{Example}

Remark: 

For any position $(i, j) \in \{1, \dots, m + 1\} \times \{1, \dots, n + 1\}$ we call $(i - 1, j)$, $(i, j - 1)$ and $(i - 1, j - 1)$ the top-left(tl) contigous positions. (Similar for top-right(tr), bottom-left(bl) and bottom-right(br)). 

\begin{define}[Scanning strategy \cite{journals/tcs/AnselmoGM09}]
	A scanning strategy is a next-position function $\mathfrak{s}$, where the corresponding sequence of visited positions $V(m, n) = V_{\mathfrak{s}, k}(m, n) = (v_1(m, n), \dots, v_k(m, n))$ at step $k = (m + 2) \cdot (n + 2)$ satisfies: 
	\begin{itemize}
		\item $v_1(m, n)$ is a corner. 
		\item $V(n, m)$ is a permutation of $P(n, m)$
		\item For any $k = 2, \dots (m + 2) \cdot (n + 2)$ the tl-(tr-, bl-, br-)contiguous positions of $v_k(m, n)$ are all in $V_{\mathfrak{s}, k}(m, n)$. 
	\end{itemize}
\end{define}

\pagebreak

A scanning strategy is called: 
\begin{itemize}
	\item \emph{continuous}, if for any $k = 2, \dots (m + 2) \cdot (n + 2)$ $v_k(m, n)$ is a contiguous position of $v_{k - 1}(m, n)$ or $v_k(m, n)$ and $v_{k - 1}(m, n)$ are at the border of the image. 
	\item \emph{normalized}, if $v_{(m + 2) \cdot (n + 2)}$ is a corner. 
\end{itemize}

\begin{Example}
	\label{example_scanning_strategy_row}
	\begin{align*}
		\mathfrak{s}_{row}(i, j, m, n) = \left\{\begin{tabular}{lr}
			(i, j + 1) & \text{ if } j $\leq$ n \\
			(i + 1, 1) & \text{ if } j = n + 1 \text{ and }  i $\leq$ m. 
		\end{tabular}\right.
	\end{align*}
\end{Example}

\begin{define}[Direction of scanning strategies \cite{journals/tcs/AnselmoGM09}]
	A scanning strategy $\mathfrak{s}$ is tl2br-directed, if for any $(m, n) \in \mathbb{N} \times \mathbb{N}$ and $k = 1, \dots, (m + 2) \cdot (n + 2)$ the top-left-contiguous positions of $v_k(m, n)$ are in $V_{\mathfrak{s}, k}(m, n)$. 
\end{define}

Similar for any corner-2-corner direction. 

\begin{Example}
	$\mathfrak{s}_{row}$ is a tl2br-directed scanning strategy. 
\end{Example}

\begin{define}[Tiling Automaton (TA) \cite{journals/tcs/AnselmoGM09}]
	$\mathcal{A} = (T, \mathfrak{s}, D_0, \delta)$ is a tiling automaton of type tl2br, where
	\begin{itemize}
		\item $T = (\Sigma, \Gamma, \Theta, \pi)$ is a tiling system
		\item $\mathfrak{s}$ is a tl2br-directed scanning strategy. 
		\item $D_0$ is an initial data structure, which supports $\mathtt{state_1}(D)$, $\mathtt{state_2}(D)$, $\mathtt{state_3}(D)$ and $\mathtt{update}(D, \gamma)$ for any data structure $D$ and $\gamma \in \Gamma \cup \{\#\}$
		\item $\delta: (\Gamma \cup \{\#\})^3 \times (\Sigma \times \{\#\}) \rightarrow 2^{\Gamma \cup \{\#\}}$ is a partial transition function with 
		
		$\gamma_4 \in \delta(\gamma_1, \gamma_2, \gamma_3, \sigma)$ if 
		\begin{tabular}{|c|c|}
			\hline
			$\gamma_1$ & $\gamma_2$ \\
			\hline
			$\gamma_3$ & $\gamma_4$ \\
			\hline
		\end{tabular} $\in \Theta$
		and $\pi(\gamma_4) = \sigma$ if $\sigma \in \Sigma$, $\gamma_4 = \#$ otherwise. 
	\end{itemize}
\end{define}

This can also be done for any corner-2-corner direction. A tiling automaton is a tiling automaton of type d, for any type d. 


\begin{itemize}
	\item A configuration in the automaton is a quadruple $(p, i, j, D)$, with the picture $p$, the position $(i, j)$ and the data structure $D$. 
	\item We define a relation on configurations as follows: $(p, i, j, D) \vdash (p, i', j', D')$  when $\mathfrak{s}(i, j, m, n)$ and $\delta(\mathtt{state_1}(D), \mathtt{state_2}(D), \mathtt{state_3}(D), p(i, j))$ are both defined and
	\begin{itemize}
		\item $(i', j') = \mathfrak{s}(i, j, m, n)$ and $D'$ is the datastructure after calling $\mathtt{update}(D, \gamma_4)$ with $\gamma_4 \in \delta(\gamma_1, \gamma_2, \gamma_3, p(i, j))$
	\end{itemize}
	\item The automaton accepts a picture $p$, if there exists a computation $(p, i_0, j_0, D_0) \vdash^* (p, i', j', D')$ with $(i', j')$ is the last position in $V_{\mathfrak{s}, (m + 2) \cdot (n + 2)}(m, n)$. 
\end{itemize}

\begin{Example}
	Let $T = (\Sigma, \Gamma, \Theta, \pi)$ be a tiling system for a language L. We construct a tiling automaton $\mathcal{A}_{row} = (T, \mathfrak{s}_{row}, D_{row_0}, \delta_{row})$, based on $T$ and the scanning strategy $\mathfrak{s}_{row}$ of example~\ref{example_scanning_strategy_row}.
	\begin{itemize}
		\item The datastructure is a list of size $m + 3$ (initially filled with $\#'s$)
		\item $\mathtt{state_1}(D)$, $\mathtt{state_2}(D)$ and $\mathtt{state_3}(D)$ returns the first, second and last element of the list. 
		\item $\gamma_4 \in \delta(\gamma_1, \gamma_2, \gamma_3, p(i, j))$ if 
		\begin{tabular}{|c|c|}
			\hline
			$\gamma_1$ & $\gamma_2$ \\
			\hline
			$\gamma_3$ & $\gamma_4$ \\
			\hline
		\end{tabular} $\in \Theta$
		and $\pi(\gamma_4) = p(i, j)$ if $p(i, j) \in \Sigma$, $\gamma_4 = \#$ otherwise. 
		\item $\mathtt{update}(D, \gamma_4)$ deletes the first element in the list ($\gamma_1$) and appends $\gamma_4$. 
	\end{itemize}	 
\end{Example}

\begin{thm}
	The class of languages accepted by tiling automata is the class REC. 
\end{thm}

\end{frame}